\input{header.tex}

\begin{document}

Простое число: не имеет делителей, кроме себя и 1, и не равно 1.

\begin{equation}

ОТА. Для \forall n \in N, n\geq 2, \exists p_1, \cdots, p_s: 

n = p_1 \cdot p_2 \cdot \ldots \cdot p_s. Этот набор единственный с точностью до перестановки множителей.

n = p_1^a_1 \cdot \ldots \cdot p_k^a_k - канонисечкое разложение.

Пояснение к д-ву ОТА.

\exists -ние почти очевидно. Если n простое, то все доказано.

Если n составное, p_1 \cdot n_1 = n и.т.д

Единственное n = p_1 \cdot p_2 \ldots \cdot p_s = q_1 \cdot \ldots \cdot q_t

Наибольний общий делитель a, b \in N  (a, b)
(a, b) = 1 \rightarrow a и b взаимно просты.

Наименьшее общее кратное a, b : [a, b]

Функция Эйлера \phi (n) - количество чисел m \leq n : (m, n) = 1
Пусть n = p_1^a_1 \cdot \ldots \cdot p_n^a_n. Тогда
\phi (n) = n \cdot (1 - \frac{1}{p_1}) \cdot (1 - \frac{1}{p_2}) \ldots \cdot (1 - frac{1}{p_s})

Сравнения по модулю.

a сравнимо с b по модулю m (a \eq b (\mod n)) <==> a-b делится на m.

Свойства:
\begin{itemize}
  \item Если a - то \forall c a + c = b + c
  \item Если a = b , то \forall c ac = bc (mod m)
  \item Если a \eq b(m), c \eq d(m), то a + c \eq b + d(m)
  \item Если ac \eq bd(m)
  \item Сравнение по модулю является отношение эквивалетности на Z.
\end{itemize}

По ОТМ Z распадается на классы эквивалетности. Множество классов эквивалетности по подулю m обозначают Z_m.

{1, \ldots , m} - полная система вычетом по модулю m.

Множество чисел от 1 до m, взаимно простых с m.

Пусть p - простое число, а число a : (b, p) = 1. Тогда a^(p-1) \eq 1(p) (Малая т. Ферма)

Доказательство(комбинаторное) a^(p-1) = 1(p) \leftarrow a^p \eq a(p)
a^p = (1 + 1 + \ldots + 1)^p = 1^p + \ldots + 1^p + Sum(n1, n2, \ldots, na) n1 + .. + na = p)
P(n_1, \ldots , n_a) \eq a(p)

Теорем Эйлера. Пусть m \in \myN, (a,m) = 1.
Тогда a^\phi(m) \eq 1(m)

Лемма: Пусть x пробегает приведенную систему вычетов по модулю m. Пусть (a,m) = 1 Тогда a \cdot x тоже пробегает приведенную систему вычетов.

Доказательство.

Предположим, что a\cdot $x_1$ \eq a\cdot $x_2$ (m)
где $x_1$, $x_2$ - различные элементы приделенной системы вычетов.
Тогда a($x_1$ - $x_2$) \eq 0(m), но (a, m) = 1 \rightarrow x_1 - x_2 \eq 0(m)

Доказательсво т. Эйлера x_1, \ldots , x_\phi(m) - минимальные положительные вычеты по модулю m, взаимно простые с m. по лемме {ax_1, \ldots , a_\phi(m)} = {x_1, \ldots , x_\phi(m) }

\rightarrow x1 \cdot \ldots \cdot x_\phi(m) \eq a_1 x_1 \cdot \ldots \cdot ax_\phi(m) = a^(\phi(m))


(a^(\phi(m)) - 1) \cdot x_1 \ldots x_\phi(m) \eq 0(m) \rightarrow a^(\phi(m)) - 1 \eq 0(m)

Многочлен от нескольких переменных.

Пример. Переменных 2 штуки - x, y/
10 x^3 y + \pi x^17 y^31 - e y^19 \ldots

Сумма с числовыми коэффициентами выражений вида x^k y^l, k \in \myN, l \in \myN.
Общий случай: x_1, \ldots, x_n
Одночлен(моном): x_1^k_1 x_2^k_2 \ldots x_n ^ k_n , k_i \in \myN
Многочлен(полином): сумма мономов.

deg F = max {k_1 + \ldots + k_n} (степень многочлена)

Пусть дан многочлен F от n переменных. Рассмотрим F(x_1, \ldots, x_n) \eq 0(p), p - простое число, x_i \in \myZ_p.

V_p - число решений этого сравнения (2 решения не различаются, если x_1 \eq y_1(p), \ldots, x_n \eq y_n(p)

Теорема Шевалле: Пусть deg F < n. Тогда N_p \eq 0(p)

\end{equation}

\end{document}
